class_name QuadTree extends Node

const MAX_DEPTH = 5 # 最大深度

var boundary: Rect2 # 管理区间
var capacity: int # 节点存储容量上限
var objs: Array[QuadTreeObj] # 节点存储对象
var depth: int # 节点深度
var divided: bool # 是否被分割
var northeast: QuadTree # 东北节点
var northwest: QuadTree # 西北节点
var southeast: QuadTree # 东南节点
var southwest: QuadTree # 西南节点

# 构造函数
func _init(_boundary: Rect2, _capacity: int = 2, _depth: int = 1) -> void:
  boundary = _boundary
  capacity = _capacity
  objs = []
  divided = false
  depth = _depth

  # 分割方法
func _subdivide() -> void:
  var X = boundary.position.x
  var Y = boundary.position.y
  var W = boundary.size.x / 2
  var H = boundary.size.y / 2
  var subDepth = depth + 1
  northeast = QuadTree.new(Rect2(X + W, Y, W, H), capacity, subDepth)
  northwest = QuadTree.new(Rect2(X, Y, W, H), capacity, subDepth)
  southeast = QuadTree.new(Rect2(X + W, Y + H, W, H), capacity, subDepth)
  southwest = QuadTree.new(Rect2(X, Y + H, W, H), capacity, subDepth)
  divided = true


# 插入对象
func insert(obj: QuadTreeObj) -> bool:
  # 判断是否在边界内
  if not boundary.has_point(obj.position): return false
  # 未满直接插入
  # 即使已满，如当前已是最深节点，也插入（最大深度用于避免过深递归）
  if objs.size() < capacity or depth == MAX_DEPTH:
    objs.append(obj)
    return true
  else:
    # 分割
    if not divided:
      _subdivide()
      divided = true

    if northeast.insert(obj): return true
    if northwest.insert(obj): return true
    if southeast.insert(obj): return true
    if southwest.insert(obj): return true
  return false

# 移除对象
func remove(obj: QuadTreeObj) -> bool:
  if obj in objs:
    objs.erase(obj)
    tryMerge()
    return true

  if divided:
    if northeast.remove(obj): return true
    if northwest.remove(obj): return true
    if southeast.remove(obj): return true
    if southwest.remove(obj): return true

  return false

# 更新对象
func update(obj: QuadTreeObj) -> bool:
  if obj in objs:
    objs.erase(obj)
    objs.append(obj)
    return true

  if divided:
    if northeast.update(obj): return true
    if northwest.update(obj): return true
    if southeast.update(obj): return true
    if southwest.update(obj): return true
  return false


# 尝试合并子节点
func tryMerge() -> void:
  if !divided: return
  if northeast.divided or northwest.divided or southeast.divided or southwest.divided: return
  if northeast.objs.size() + northwest.objs.size() + southeast.objs.size() + southwest.objs.size() + objs.size() > capacity: return
  _clearChildren()

# 清除子节点
func _clearChildren() -> void:
  objs += northeast.objs + northwest.objs + southeast.objs + southwest.objs
  northeast = null
  northwest = null
  southeast = null
  southwest = null
  divided = false

# 查询矩形范围内的对象
func query(rect: Rect2, founds: Array) -> void:
  if not boundary.intersects(rect): return

  for obj in objs:
    if rect.has_point(obj.position):
      founds.append(obj)

  if divided:
    northeast.query(rect, founds)
    northwest.query(rect, founds)
    southeast.query(rect, founds)
    southwest.query(rect, founds)